The present invention is generally directed to pseudorandom pattern generators using linear feedback shift registers. More particularly, the present invention is directed to means and a method for varying the phase shift between adjacent output lines of shift register cells. The invention is particularly useful in generating test patterns for complex integrated circuit logic configurations.
Because of the increased complexity and density of integrated circuit chips and chip configurations, it is becoming increasingly important to be able to adequately test these circuits and their logical functions. The tests contemplated herein may in fact be carried out prior to certification of various chip components or may be carried out in the field, especially during field diagnostic operations.
Because combinatorial and sequential logic circuits have increased in complexity, the number of signal inputs supplied to these circuits has risen correspondingly. As a result of this increase, it often becomes impossible, or at least certainly impractical, to exhaustively test all of the different signal input patterns that could be applied to a circuit. While it is sometimes possible to break down the testing problem so as to reduce the number of inputs, this is not always possible nor may it be completely desirable in all circumstances. Accordingly, an alternate approach to testing has the generation of random test vectors or patterns which are applied to certain input test lines.
One of the methods for generating such test vectors involves the utilization of linear feedback shift registers (LFSRs). In general, linear feedback shift registers are well known in the electrical arts, particularly for their role in the design of circuits which implement error correction and detection. Typically LFSRs comprise a sequence of chained data flip-flops, together with appropriate clocking signals for shifting binary data from one shift register cell to the next. Without limitation, and solely for the purposes of illustration, the LFSR can be thought of as shifting binary digits or bits from the left to the right. In LFSRs output signals from one or more data storage cells in a chain are fed back to preceding cells in the chain, that is to cells to the left of the cells from which the output is taken. These feedback connections are generally made through exclusive-OR gates which in actuality implement a modulo 2 addition operation. As a result of the feedback arrangement, the sequence of patterns of 1's and 0's that the shift register cells exhibit is made to be different. In particular, by an appropriate choice of feedback arrangements, it is often possible to cause the linear feedback shift register to cycle through binary representations of the numbers 0 through 2.sup.n-1, where n is the number of cells in the shift register. It is noted however that because of the feedback arrangement, the shift register patterns do not cycle in numeric order but effectively generate a bit pattern representative of a randomly selected one of the integers from 0 through 2.sup.n-1. Accordingly, linear feedback shift registers of the sort just described have played a significant role in the generation of random patterns of binary vectors. It is these patterns of output signals from the shift register cells which may be supplied to complex logic circuitry for the purpose of effecting a testing function.
Fundamental design philosophies for self testing are described in the text "Built-in Test for VLSI Pseudorandom Techniques" by Paul H. Bardell, William H. McAnney and Jacob Savir as published by John Wiley & Sons, Inc., copyright 1987. It is noted that the inventor herein is one of the aforementioned authors. Chapter 2 of this text illustrates both ad hoc design methodologies and structured design methodologies for self testing. In particular, section 2.2 of this text notes that if the values of certain internal registers can be controlled and observed easily, then the generation of test sequences is reduced to a problem of combinatorial logic. This approach offers significant advantages. In particular, built-in test structures are easily constructed and, more importantly, the ground rules for structured designs almost variably result in synchronous logic which has a reduced and well defined timing dependency. In particular, one of the structured design techniques which is especially relevant to the present invention is the level sensitive scan design (LSSD) methodology. This enables separation of combinational logic and storage elements for test purposes. The shift register latch (SRL) storage elements in this arrangement then become pseudo-inputs for the purpose of test application and pseudo-outputs for the purpose of test observation.
When linear feedback shift registers are employed as parallel sequence pattern generators, the most natural implementation of LSSD is one in which the output from each storage cell of the shift register set is fed into one of many scan paths. In this method, the LFSR shifting clocks and the scan path shifting clocks are the same. This direct implementation results in an array of pseudorandom bits that unfortunately has a structural dependency. If adjacent scan paths are provided with input signals from contiguous shift register stages, the same values appear in adjacent scan paths but off-set by one shift. In particular, if a 2.times.2 window is placed anywhere on the array formed by the scan paths, only one-half of the possible 2.times.2 binary arrays appear as the linear feedback shift register passes through its cycle. If a 3.times.3 window is considered, only one-fourth of the possible binary arrays appear. Larger windows have proportionately smaller coverages. This is a serious problem for built-in test applications which the present invention solves.
It is noted that a simple reassignment of scan latches for the inputs is a solution which is not allowed under the ground rules derived from certain design philosophy considerations. In particular, the sequence generator should be one such that reassignment is not necessary to insure adequate coverage of the pseudorandom pattern set. Thus something more than a simple linear feedback shift register with parallel output feed is required as a suitable sequence generator. It is this problem which the present invention seeks to solve.
The method and apparatus of the present invention are therefore seen to be generally applicable to the generation of uncorrelated parallel test vector sequences for diagnosing physical and functional problems in both combinatorial and sequential logic circuits. Furthermore, the present invention is generally applicable not only to off chip testing, but is particularly applicable to built-in testing in which the circuitry of the present invention is incorporated on a chip along with the circuitry which is being tested.